# 给定一个单链表 L 的头节点 head ，单链表 L 表示为： 
# 
#  
# L0 → L1 → … → Ln - 1 → Ln
#  
# 
#  请将其重新排列后变为： 
# 
#  
# L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 
# 
#  不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 
# 
#  
# 
#  示例 1： 
# 
#  
# 
#  
# 输入：head = [1,2,3,4]
# 输出：[1,4,2,3] 
# 
#  示例 2： 
# 
#  
# 
#  
# 输入：head = [1,2,3,4,5]
# 输出：[1,5,2,4,3] 
# 
#  
# 
#  提示： 
# 
#  
#  链表的长度范围为 [1, 5 * 10⁴] 
#  1 <= node.val <= 1000 
#  
# 
#  Related Topics 栈 递归 链表 双指针 👍 1550 👎 0
from typing import Optional

from LeetCode.Test.LinkTool import ListNode, LinkedListTool, Link


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        stack = []
        curr = head
        # 这个循环将全部节点断键后压入栈内
        while curr:
            next_node = curr.next
            # 断链，目的是只存一个节点
            curr.next = None
            stack.append(curr)
            curr = next_node
        start = 0
        end = len(stack) - 1
        dummy = ListNode(-1)
        cur = dummy

        # 这个例用stack的随机访问，拿出节点重新组成链表
        while start < end:
            cur.next = stack[start]
            cur = cur.next
            cur.next = stack[end]
            cur = cur.next
            start += 1
            end -= 1
        if len(stack)%2==1:
            cur.next = stack[end]
        return dummy.next


# leetcode submit region end(Prohibit modification and deletion)
Link.each(Solution().reorderList(LinkedListTool([1, 2, 3, 4,5]))
          )
